#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);

    return node;
}

ListNode *reverse(ListNode *head, ListNode *nextEnd)
{
    ListNode *next = nextEnd;
 
    while(head->next != nextEnd) {
	    ListNode *tmp = head->next;
	    head->next = next;
	    next = head;
	    head = tmp;
    } 
    head->next = next;
    return head;
}


//test on 1337 online judge and pass all the test
ListNode* reverse(ListNode *head, int start, int end)
{
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *cur = dummy, *preEnd, *next;

    for (int i = 0; i < start; i++) {
	    preEnd = cur;
	    cur = cur->next; 
        if (!cur) return head;
    }

    ListNode *nextEnd = cur;
    for (int i = start; i<= end; i++) {
	    nextEnd = nextEnd->next;
        if (!nextEnd && i != end) return head;
    }

    ListNode *newHead = reverse(cur, nextEnd);
    preEnd->next = newHead;
    return dummy->next;
}


//add some new code
ListNode* reverse(ListNode *head, ListNode *nextStart)
{
    ListNode *prev = NULL, *saveHead = head;
    while (head != nextStart) {
        ListNode *nxt = head->next;
        head->next = prev;
        prev = head;
        head = nxt;    
    }   
    saveHead->next = nextStart; 
    return prev;
}
 
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode Dummy(0);
        ListNode *h = &Dummy;
        h->next = head;
        ListNode *preStart = h, *nextStart = h;
        while(--m > 0) {
            preStart = preStart->next;
        }   
        n++;
        while(n--> 0) {
            nextStart = nextStart->next;
        }
        preStart->next = reverse(preStart->next, nextStart);
        return h->next;
    }
};


//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    cout << "-----------------Test 1--------------------" << endl;
    int data[] = {1,2,3,4,5};
    ListNode *list1, *list2;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    list2 = reverse(list1, 2, 4);
    while(list2) {
        cout << list2->val << " ";
        list2 = list2->next;
    } 

    cout << endl;

}
